package leetcode.Hot100;

/**
 * @author Cheng Jun
 * Description: 给你一个整数 n ，对于 0 <= i <= n 中的每个 i ，计算其二进制表示中 1 的个数 ，
 * 返回一个长度为 n + 1 的数组 ans 作为答案。
 * @version 1.0
 * @date 2021/11/19 15:40
 */
public class countBits {

    public static void main(String[] args) {
        countBits(5);
    }

    static int[] countBits(int n) {
        int[] bits = new int[n + 1];
        for (int i = 0; i <= n; i++) {
            bits[i] = Integer.bitCount(i);
        }
        return bits;
    }

    // Brian Kernighan(布莱恩·柯林汉)算法:对于任意整数 x，令 x=x&(x-1)，
    // 该运算将 x 的二进制表示的最后一个 1 变成 0。因此，对 x 重复该操作，直到 x 变成 0，则操作次数即为 x 的「1 比特数」。
    // AND 操作对左边的数没有影响
    // AND 操作使得每次抹掉最右边的1
    static int[] countBits1(int n) {
        int[] bits = new int[n + 1];
        for (int i = 0; i <= n; i++) {
            int temp = i;
            int bitCount = 0;
            while (temp > 0) {
                temp = temp & (temp - 1);
                bitCount++;
            }
            bits[i] = bitCount;
        }
        return bits;
    }

    // 这个其实就是动态规划
    // 奇偶性 规律：2n + 1 的 一比特数 总比 2n 多一个，2n 的 一比特数 和 n 相同。
    static int[] countBits3(int n) {
        int[] bits = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            bits[i] = bits[i / 2] + (i & 1);
        }
        return bits;
    }
}
